# encoding=utf-8
# ---------------------------------------
#   版本：0.1
#   日期：2016-11-10
#   作者：九茶<bone_ace@163.com>
# ---------------------------------------

import redis
from hashlib import md5


class SimpleHash(object):
    def __init__(self, cap, seed):
        self.cap = cap
        self.seed = seed

    def hash(self, value):
        ret = 0
        for i in range(len(value)):
            ret += self.seed * ret + ord(value[i])
        return (self.cap - 1) & ret


class BloomFilter(object):
    """
    Bloomfilter算法是有漏失概率的（即不存在的会误判为存在），在保证漏失率小于万分之一的情况下，
    一个blockNum可满足7千万条数据的去重，一个blockNum占用256M内存（注意Linux如果开了自动持久化，redis占用内存会加倍）
    """
    def __init__(self, conn=None, blockNum=1, key='bloomfilter'):
        self.server = conn
        self.bit_size = 1 << 31  #Redis的String类型最大容量为512M,现使用256M,256*1024*1024*8(b)
        self.seeds = [5, 7, 11, 13, 31, 37, 61]#数组长度越大,查询效率越低,但错误率越低
        self.key = key
        self.blockNum = blockNum#去重模块,随着去重数量的增多可以增加blockNum个数
        self.hashfunc = []
        for seed in self.seeds:
            self.hashfunc.append(SimpleHash(self.bit_size, seed))

    def isContains(self, str_input):
        if not str_input:
            return False
        m5 = md5()
        m5.update(str_input.encode("utf-8"))
        str_input = m5.hexdigest()
        ret = True
        name = self.key + str(int(str_input[0:2], 16) % self.blockNum)
        for f in self.hashfunc:
            loc = f.hash(str_input)
            ret = ret & self.server.getbit(name, loc)
        return ret

    def insert(self, str_input):
        m5 = md5()
        m5.update(str_input.encode("utf-8"))
        str_input = m5.hexdigest()
        name = self.key + str(int(str_input[0:2], 16) % self.blockNum)
        for f in self.hashfunc:
            loc = f.hash(str_input)
            self.server.setbit(name, loc, 1)



if __name__ == '__main__':
    bf = BloomFilter(conn=redis.StrictRedis(host='127.0.0.1', port=6379, db=0, password="li1234redis"))
    print(bf.isContains("222"))

